package com.example.graph;

/**
 * N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。
 * 一次交换可选择任意两人，让他们站起来交换座位。
 * 人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，
 * 第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)
 * 这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
 * <p>
 * 示例 1:
 * 输入: row = [0, 2, 1, 3]
 * 输出: 1
 * 解释: 我们只需要交换row[1]和row[2]的位置即可。
 * <p>
 * 示例 2:
 * 输入: row = [3, 2, 0, 1]
 * 输出: 0
 * 解释: 无需交换座位，所有的情侣都已经可以手牵手了。
 * <p>
 * 说明:
 * len(row) 是偶数且数值在 [4, 60]范围内。
 * 可以保证row 是序列 0...len(row)-1 的一个全排列。
 */
public class Leetcode765_MinSwapsCouples {
    public static void main(String[] args) {
        int[] row;

//        row = new int[] {3, 2, 0, 1};
//        row = new int[] {0, 2, 1, 3};
        row = new int[]{6, 3, 0, 2, 1, 4, 5, 7};

        System.out.println(new Solution().minSwapsCouples(row));

    }

    static class Solution {
        public int minSwapsCouples(int[] row) {
            return minSwapsCouples3(row);
        }

        /**
         * 解法三:并查集
         *
         * 将所有人员看成节点，每对情侣之间用一条线连接，则所有情侣构成了一个具有N个连通分量的图
         * 每次交换都是为了至少能成功让一对情侣牵手，否则本次交换没有任何意义
         * 把每次交换看作连通分量的合并（并查集），解决思路如下：
         *    一：交换次数=合并次数
         *    二：交换次数=N（原有连通分量个数）- 最后剩余连通分量个数
         *
         * 关键点：
         * 1.如何判断两个情侣（A，B）是一对？
         * 把每对情侣看作一组，并按组编号：
         * (0,1)(2,3)(4,5)(6,7)(...,...)(2N-2,2N-1) 每个人的编号
         *   0    1    2    3    ...       N-1   情侣组编号
         *
         * 2.如何求解交换次数，两个逻辑：
         *   方式一:每合并一次，即对应一次交换：初始count=0
         *          count++; // 交换次数
         *   方式二:每合并一次，连通分量少一个：初始count=N
         *         count--; // 剩余连通分量
         *         N - count; // 交换次数
         * 情侣编号和组编号的关系是：组编号 = row[i] / 2
         *
         *
         * @param row
         * @return
         */
        public int minSwapsCouples3(int[] row) {
            int coupleNum = row.length / 2; // 总共的情侣对数
            UnionFindSet uf = new UnionFindSet(coupleNum);

            for (int i = 0; i < row.length; i += 2) {
                // 尝试合并相邻的两个情侣
                // 相邻两个元素如果已经是匹配的情侣(即row[i] / 2 == row[i + 1] / 2) 此时不会进行合并
                uf.union(row[i] / 2, row[i + 1] / 2);

            }
            return coupleNum - uf.getCount();

        }

        private class UnionFindSet {
            int[] parent;
            int[] rank; // rank的操作不是必须的
            int count; // 集合数量

            public UnionFindSet(int size) {
                parent = new int[size];
                rank = new int[size];

                for (int i = 0; i < size; i++) {
                    parent[i] = i;
                    rank[i] = 1;
                }
                this.count = size;
            }

            public int find(int node) {
                if (parent[node] != node)
                    parent[node] = find(parent[node]);

                return parent[node];
            }

            public void union(int x, int y) {
                int rootX = find(x);
                int rootY = find(y);
                if (rootX == rootY) {
                    return;
                }

                if (rank[rootX] == rank[rootY]) {
                    parent[rootX] = rootY;
                    rank[rootY]++;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                }
                count--;
            }

            public int getCount() {
                return count;
            }
        }

        /**
         * 解法二:使用hash表优化暴力法
         * <p>
         * 思路:
         * 内层循环要依次遍历很耗时
         * 使用一个数组(hash表)记录每个人所在的索引位置，这样就可以直接定位到该元素的位置省去了遍历的时间
         *
         * @param row
         * @return
         */
        public int minSwapsCouples2(int[] row) {
            int[] sites = new int[row.length];
            for (int i = 0; i < row.length; i++) {
                sites[row[i]] = i;
            }

            int count = 0;
            for (int i = 0; i < row.length; i += 2) {
//                int matchedFri = (row[i] % 2 == 0) ? (row[i] + 1) : row[i] - 1; // 得到与当前编号配对的编号
                int matchedFri = row[i] ^ 1; // 等效上面的代码
                int index = sites[matchedFri]; // 获得与当前编号配对的编号的索引位置
                if (index != i + 1) { // 当前的情侣对不匹配时才要进行交换
                    count++;
                    // 进行交换
                    row[index] = row[i + 1];
                    row[i + 1] = matchedFri;
                    sites[row[index]] = index; // 将下一个元素的索引值更新成与当前编号配对的编号的索引
//                    sites[matchedFri] = i + 1; // 可以不更新与当前编号配对的编号的索引位置信息
                }
            }

            return count;

        }

        /**
         * 解法一:暴力法
         * 贪心策略
         * 外层遍历每个人，内层查找每个人(A)的情侣(B)，步长为2
         * 找到情侣 B 后，交换 B 与紧随 A 之后的位置
         * A 为偶数，情侣 B 为 A+1 A 为奇数，情侣 B 为 A 1
         * 外层循环步长为 2
         * 统计交换次数并返回
         * <p>
         * 因为初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
         * 即要根据偶数索引上的人(row[2i])去找到与之相匹配的情侣(row[2i + 1])
         * 当row[2i]为奇数时，与之匹配的情侣编号为row[2i] - 1
         * 当row[2i]为偶数时，与之匹配的情侣编号为row[2i] + 1
         * 遍历后面的所有元素，找到与之匹配的编号并进行交换
         *
         * @param row
         * @return
         */
        public int minSwapsCouples1(int[] row) {
            int count = 0;
            for (int i = 0; i < row.length; i += 2) {
                int matchedFri = (row[i] % 2 == 0) ? (row[i] + 1) : row[i] - 1; // 得到与当前编号配对的编号
                // int matchedFri = row[i] ^ 1; // 等效上面的代码
                if (matchedFri != row[i + 1]) { // 当前的情侣对不匹配时才要进行交换
                    for (int j = i + 2; j < row.length; j++) {
                        if (row[j] == matchedFri) {
                            count++; // 交换次数+ 1
                            // 进行交换操作
                            row[j] = row[i + 1];
                            row[i + 1] = matchedFri;
                            break;
                        }
                    }
                }
            }

            return count;
        }
    }
}

